package lib

func init() {
	Probs = append(Probs, Problem{
		Num:         76,
		Discription: "最小覆盖子串",
		Level:       3,
		Labels: map[string]int{
			"双指针滑动": 1,
			"字符串":   1,
			"滑动窗口":  1,
		},
	})
}

//思路：每匹配到一个ch，就在满足最小覆盖子串的条件下尝试缩小左边界
//通过count判断所有字符是否已经匹配完毕（是不是覆盖子串），匹配完毕的话更新最小子串
func MinWindow(s string, t string) string {
	if len(s) < len(t) {
		return ""
	}

	chMap := make(map[byte]int, 0)
	for j := range t {
		chMap[t[j]]++
	}
	count := len(chMap)

	left := 0
	right := 1
	start := -1
	end := len(s)
	for ; right <= len(s); right++ {
		ch := s[right-1]
		_, exist := chMap[ch]
		if !exist {
			continue
		}

		chMap[ch]--
		//必须放在chMap[ch]--后面，保证是从1减到0的
		if chMap[ch] == 0 {
			count--
		}
		//尝试缩小左边界
		for left < right {
			leftCh := s[left]
			if _, exist := chMap[leftCh]; !exist {
				left++
				continue
			}

			if chMap[leftCh] < 0 {
				chMap[leftCh]++
				left++
			} else {
				break
			}
		}

		//如果是覆盖子串，更新最小子串
		if count == 0 && right-left < end-start {
			end = right
			start = left
		}
	}

	if start == -1 {
		return ""
	}

	return s[start:end]
}
